// Problem: 
// Contest: 
// URL: 
// Memory Limit: 
// Time Limit: 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
signed main()
{
	int t=1;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> v(n+1);
		for(int i=1;i<=n;i++)
		{
			cin>>v[i];
		}
		int l,r;
		bool f=0;
		for(int i=1;i<=n;i++)
		{
			if(v[i]<=0&&f)
			{
				r++;
			}
			if(v[i]<=0&&!f)
			{
				r=l=i;
				f=1;
			}
			if(v[i]>0&&f)
			{
				f=0;
				if(r-l+1>=2)
				{
					for(int j=l;j<=r;j++)
					{
						v[j]=0;
					}
				}
				else
				{
					if(i-3<=0||v[i-3]>0)
					{
						if(v[i-1]+v[i]<0)
						{
							if(i-2>0&&v[i-1]+v[i-2]<0)
							{
								if(v[i]<v[i-2])
									v[i]=v[i-1]=0;
								else
									v[i-1]=v[i-2]=0;
							}
							else v[i]=v[i-1]=0;
						}
						else if(i-2>0&&v[i-1]+v[i-2]<0)
						{
							v[i-2]=v[i-1]=0;
						}
					}
					else 
					{
						if(v[i-3]+v[i-2]+v[i-1]<0)
						{
							if(v[i-1]+v[i]<0)
							{
								if(v[i]<v[i-3]+v[i-2])
									v[i]=v[i-1]=0;
								else
									v[i-3]=v[i-1]=v[i-2]=0;
							}
							else v[i-3]=v[i-1]=v[i-2]=0;
						}
					}
				}
			}
		}
		if(f)
		{
			f=0;
			if(l-r+1>=2)
			{
				for(int j=l;j<=r;j++)
				{
					v[j]=0;
				}
			}
			else
			{
				if(v[n-1]+v[n]<0)
				{
					v[n]=v[n-1]=0;
					if(v[n-2]<0)v[n-2]=0;
				}
				else if(v[n-2]+v[n-1]+v[n]<0)
				{
					v[n-2]=v[n]=v[n-1]=0;
				}
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			ans+=v[i];
		}
		cout<<ans<<endl;
	}
	return 0;
}
